# 北京八维研修学院人工智能学院1906A班学员
# 2021年1月20日 星期三 下午17:28
# 听许朋飞老师讲解python基础之递归函数后做出
# 不足之处请各位不吝赐教
# 本代码侧重展示解题细节，没有刻意追求效率

xpillars = {'A', 'B', 'C'}  # 汉诺塔的三个柱子


def xhanoi(xtop, xbottom, xsrc='A', xdest='C'):
    '''
    解汉诺塔

    :param xtop: 移动的“整体”的最顶层，只能是1或xbottom
    :param xbottom: 移动的“整体”的最底层，正整数
    :param xsrc: 从哪个柱子移动（起始柱子）
    :param xdest: 移动到哪个柱子（目标柱子）
    :return: None
    '''
    if not (xtop == 1 and xbottom >= xtop or 1 < xtop == xbottom) \
            or not (xsrc in xpillars) \
            or not (xdest in xpillars):
        print('非法参数')
        return
    if xtop == xbottom:  # 仅移动一个盘子
        print(xtop, xsrc, '-->', xdest)
    else:  # 移动两个以上盘子
        xaux = (xpillars - {xsrc, xdest}).pop()  # 三个柱子里用作“中转”的柱子
        # 递归算法
        xhanoi(1, xbottom - 1, xsrc, xaux)  # 先把1到倒数第2个盘子移动到中转柱子
        xhanoi(xbottom, xbottom, xsrc, xdest)  # 移动最底下的盘子
        xhanoi(1, xbottom - 1, xaux, xdest)  # 再把1到倒数第2个盘子移动到目标柱子


if '__main__' == __name__:
    xhanoi(1, 3)  # 移动从1层到3层，从A到C。也就是求解3层汉诺塔。
